import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

/**
 * @author zx
 * @date date 2019-12-02 13:39:04
 *
 * https://leetcode-cn.com/problems/find-all-anagrams-in-a-string/
 */
public class T438 {
    public static List<Integer> findAnagrams(String s, String p){
        List<Integer> list = new ArrayList<>();
        int l = 0, r = 0;
        HashMap<Character, Integer> dictT = new HashMap<>();
        HashMap<Character ,Integer> windowCount = new HashMap<>();

        for (int i = 0; i < p.length(); i++) {
            dictT.put(p.charAt(i), dictT.getOrDefault(p.charAt(i),0) + 1);
        }

        int match = 0;
        int required = dictT.size();

        while(r < s.length()) {
            char cs_right = s.charAt(r);
            if(dictT.containsKey(cs_right)){
                windowCount.put(cs_right,windowCount.getOrDefault(cs_right,0) + 1);
                if(windowCount.get(cs_right).equals(dictT.get(cs_right))){
                    match++;
                }
            }
            while (l <= r && match == required){
                if(r - l + 1 == p.length()){
                    list.add(l);
                }
                char cs_left = s.charAt(l);
                if(dictT.containsKey(cs_left)){
                    windowCount.put(cs_left,windowCount.get(cs_left) - 1);
                    if(windowCount.get(cs_left) < dictT.get(cs_left)){
                        match--;
                    }
                }
                l++;
            }
            r++;
        }
        return list;

    }

    public static void main(String[] args) {
        String s = "baa";
        String p = "aa";

        System.out.println(findAnagrams(s, p));
    }
}
